package com.jhy.new2025.stack;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 * <p>
 * 输入: nums = [1], k = 1
 * 输出: [1]
 */
public class TopKFrequent {
    public static int[] topKFrequent(int[] nums, int k) {
        // 定义返回数组
        int[] res = new int[k];

        // 对nums的key和value进行统计
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // 定义一个优先级的队列 大根堆还是小根堆才行
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int[] array = new int[2];
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            array[0] = key;
            array[1] = value;
            // 优先级队列每次在这里就排队好了 不符合k的条件直接退出
            queue.offer(array);
            if (queue.size() > k) {
                queue.poll();
            }
        }

        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,0,1,0};
        int k = 1;
        topKFrequent(nums, k);
    }

}
